package review.Day_0406;

import java.util.Stack;

/**
 * @author zxc
 * @date 2023/04/06 21:57
 **/
public class Solution02 {
    /**
     * 思考 ：
     * 倒序遍历heights数组中所有元素，栈中存储的元素符合-从栈底到栈顶递减的条件，其真正的用处
     * ===》
     * （1）实现以O(n)时间复杂度，遍历数组中所有元素，获取以自身为起始值，遍历该元素右侧的所有元素，统计得到递增元素总数;
     * （2）暴力法 ：
     *  ===》
     *  即，遍历数组中所有元素，固定住所遍历的元素，同时遍历该元素右侧的所有元素，统计递增元素总数;
     *  时间复杂度 ：O(n^2);
     */
    public int[] canSeePersonsCount(int[] heights) {
        // 获取heights数组中的元素总数
        int len = heights.length;
        // 创建结果数组，用来存储每个对象在其右侧队列中所能够看到的对象数;
        int[] result = new int[len];
        Stack<Integer> stack = new Stack<>();
        // 逆序遍历heights数组中每个对象
        for(int i = len - 1; i >= 0 ; i--){
            result[i] = stack.size();
            while(!stack.isEmpty() && stack.peek() < heights[i]){
                stack.pop();
            }
            stack.push(heights[i]);
        }
        return result;
    }
}
